package com.its.myalgorithm.day04;

import com.its.myalgorithm.day04.ListArrayUtils;

import java.util.List;

/**
 * @projectName: dgl-algorithm
 * @package: com.its.myalgorithm.day04
 * @className: ReverseNode
 * @author: DONG GL
 * @description: TODO 单链表反转
 * @date: 2022/4/2 9:20
 * @version: 1.0
 */
public class ReverseNode {
    /**
     * 单链表反转
     *
     * @param head
     * @return
     */
    private static Node reverseLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        //head的前一个值
        Node pre = null;
        //head的下一个值
        Node next = null;
        while (head != null) {
            //取出当前链表的下一个值
            next = head.next;
            //当前链表的下一个值 指向当前head的头部
            head.next = pre;
            //当前head已经反转换完成
            pre = head;
            //head向下移动
            head = next;
        }
        return pre;
    }

    /**
     * 链表校验 反转 从数组末尾取值比较
     *
     * @param head
     * @param origin
     * @return
     */
    public static boolean checkLinkedListReverse(Node head, List<Integer> origin) {
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    /**
     * 测试
     *
     * @param args
     */
    public static void main(String[] args) {
        int len = 100;
        int maxValuse = 100;
        int testTime = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            Node node = ListArrayUtils.generateRandomLinkedList(len, maxValuse);
            List<Integer> linkedListOriginOrder = ListArrayUtils.getLinkedListOriginOrder(node);
            Node node1 = reverseLinkedList(node);
            if (!checkLinkedListReverse(node1, linkedListOriginOrder)) {
                System.out.println("链表反转错误");
            }
        }
        System.out.println("测试完毕");
    }
}
